package com.heima.algorithm.greedy;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 0-1背包问题   注：贪心算法达不到最优解
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/3 13:33
 */
public class KnapsackProblem {
    /*
     0-1 背包问题

     问题描述：
     1、n个物品都是固体，有重量和价值
     2、现在你要取走不超过 10g 的物品
     3、每次拿不拿或全拿，问能拿的最高价值是多少

     编号     名称         重量(g)       价值(元)
      0     钻戒一枚         1            1_000_000
      1     黄金一枚         4            1600
      2     红宝石戒指一枚    8            2400
      3     白银一枚         5            30


      常见贪心策略
      1、按价值排序：
          策略：选择价值最高的物品。
          不足：即使某个物品价值很高，但如果它的重量也很大，可能会导致其他更有价值的物品无法放入背包，比如此物品7g，另外两种一个5g一个4g，但是后者合起来的总价值高于前面，如果选了前面后面的不能选。
      2、按重量排序：
          策略：选择重量最小的物品。
          不足：即使某个物品重量很小，但如果它的价值很低，可能会导致总价值不高。
      3、按单位价值排序：
          策略：选择单位价值（价值/重量）最高的物品。
          不足：虽然单位价值高的物品通常是有利的，但在某些情况下，这种策略仍然可能导致次优解，比如单位价值高，但是总价值低，另一个总价值高的选不了
      所以贪心策略并不能解决此问题
     */

    /**
     * 物品类
     */
    public static class Item {
        int index;
        String name;
        double weight;
        double value;

        public Item() {
        }

        public Item(int index, String name, double weight, double value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        public double valuePerWeight() {
            return value / weight;
        }

        public String name() {
            return name;
        }

        public double value() {
            return value;
        }

        @Override
        public String toString() {
            return "{" +
                    "name='" + name + '\'' +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }

    /**
     * 选择最大价值
     * @param itemList 物品列表
     * @param totalWeight 总重量
     * @return  选择结果
     */
    public static List<Item> select(List<Item> itemList, double totalWeight) {
        // itemList.sort((item1, item2) -> Double.compare(item2.valuePerWeight(), item1.valuePerWeight()));
        itemList.sort(Comparator.comparingDouble(Item::valuePerWeight).reversed());

        List<Item> result = new ArrayList<>();
        for (Item item : itemList) {
            if (item.weight <= totalWeight){
                result.add(item);
                totalWeight -= item.weight;
            }
        }
        return result;
    }
}
